home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 9 / Night Owl CD-ROM (NOPV9) (Night Owl Publisher) (1993).ISO / 009a / tde221.zip / FINDREP.C < prev    next >
C/C++ Source or Header  |  1993-04-01  |  48KB  |  1,604 lines
  1. /*******************  start of original comments  ********************/
  2. /*
  3.  * Written by Douglas Thomson (1989/1990)
  4.  *
  5.  * This source code is released into the public domain.
  6.  */
  7.  
  8. /*
  9.  * Name:    dte - Doug's Text Editor program - find/replace module
  10.  * Purpose: This file contains the functions relating to finding text
  11.  *           and replacing text.
  12.  *          It also contains the code for moving the cursor to various
  13.  *           other positions in the file.
  14.  * File:    findrep.c
  15.  * Author:  Douglas Thomson
  16.  * System:  this file is intended to be system-independent
  17.  * Date:    October 1, 1989
  18.  */
  19. /*********************  end of original comments   ********************/
  20.  
  21. /*
  22.  * The search and replace routines have been EXTENSIVELY rewritten.  The
  23.  * "brute force" search algorithm has been replaced by the Boyer-Moore
  24.  * string search algorithm.  This search algorithm really speeds up search
  25.  * and replace operations.
  26.  *
  27.  *                  Sketch of the BM pattern matching algorithm:
  28.  *
  29.  *    while (not found) {
  30.  *       fast skip loop;    <===  does most of the work and should be FAST
  31.  *       slow match loop;   <===  standard "brute force" string compare
  32.  *       if (found) then
  33.  *          break;
  34.  *       shift function;    <===  mismatch, shift and go to fast skip loop
  35.  *    }
  36.  *
  37.  * See:
  38.  *
  39.  *   Robert S. Boyer and J Strother Moore, "A fast string searching
  40.  *     algorithm."  _Communications of the ACM_ 20 (No. 10): 762-772, 1977.
  41.  *
  42.  * See also:
  43.  *
  44.  *   Zvi Galil, "On Improving the Worst Case Running Time of the Boyer-
  45.  *    Moore String Matching Algorithm."  _Communications of the ACM_
  46.  *    22 (No. 9): 505-508, 1979.
  47.  *
  48.  *   R. Nigel Horspool, "Practical fast searching in strings." _Software-
  49.  *    Practice and Experience_  10 (No. 3): 501-506, 1980.
  50.  *
  51.  *   Alberto Apostolico and Raffaele Giancarlo, "The Boyer-Moore-Galil
  52.  *    String Searching Strategies Revisited."  _SIAM Journal on Computing_
  53.  *    15 (No. 1): 98-105, 1986.
  54.  *
  55.  *   Andrew Hume and Daniel Sunday, "Fast String Searching."  _Software-
  56.  *    Practice and Experience_ 21 (No. 11): 1221-1248, November 1991.
  57.  *
  58.  *   Timo Raita, "Tuning the Boyer-Moore-Horspool String Searching Algorithm."
  59.  *    _Software-Practice and Experience_ 22 (No. 10): 879-884, October 1992.
  60.  *
  61.  *
  62.  *                            Boyer-Moore in TDE
  63.  *
  64.  * Hume and Sunday demonstrated in their paper that using a simple shift
  65.  * function after a mismatch gives one of the fastest search times with the
  66.  * Boyer-Moore algorithm.  When searching normal text for small patterns
  67.  * (patterns less than 30 characters or so), Hume and Sunday found that the
  68.  * faster the algorithm can get back into the fast skip loop with the
  69.  * largest shift value then the faster the search.  Some algorithms can
  70.  * generate a large shift value, but they can't get back into the skip loop
  71.  * very fast.  Hume and Sunday give a simple method for computing a shift
  72.  * constant that, more often than not, is equal to the length of the search
  73.  * pattern.  They refer to the constant as mini-delta2 or md2.  From the
  74.  * end of the string, md2 is the first leftmost occurrence of the rightmost
  75.  * character.  Hume and Sunday also found that using a simple string
  76.  * compare as the match function gave better performance than using the C
  77.  * library memcmp( ) function.  The average number of compares in the slow
  78.  * loop was slightly above 1.  Calling the memcmp( ) function to compare 1
  79.  * character slows down the algorithm.  See the Hume and Sunday paper for an
  80.  * excellent discussion on fast string searching.  Incidentally, Hume and
  81.  * Sunday describe an even faster, tuned Boyer-Moore search function.
  82.  *
  83.  * Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a bug when
  84.  * building the ignore skip index array in TDE 1.3 and previous versions.
  85.  * BTW, I added assertions to those functions that build the skip index
  86.  * array to make certain that everything is everything.
  87.  *
  88.  * The Boyer-Moore search algorithm in TDE was rearranged so that it is now
  89.  * almost identical to the original version Boyer-Moore described in CACM.
  90.  * The simple shift function in TDE was replaced by the mini-delta2 shift
  91.  * function in the Hume and Sunday paper.
  92.  *
  93.  * I am not very fond of WordStar/TURBO x style search and replace prompting,
  94.  * which is used in the DTE 5.1 editor.  Once the search pattern has been
  95.  * defined, one only needs to press a key to search forwards or backwards.
  96.  * The forward or backward search key may be pressed at any time in any file
  97.  * once the pattern has been entered.  Also, the search case may be toggled
  98.  * at any time in any file once the pattern has been entered.
  99.  *
  100.  * New editor name:  TDE, the Thomson-Davis Editor.
  101.  * Author:           Frank Davis
  102.  * Date:             June 5, 1991, version 1.0
  103.  * Date:             July 29, 1991, version 1.1
  104.  * Date:             October 5, 1991, version 1.2
  105.  * Date:             January 20, 1992, version 1.3
  106.  * Date:             February 17, 1992, version 1.4
  107.  * Date:             April 1, 1992, version 1.5
  108.  * Date:             June 5, 1992, version 2.0
  109.  * Date:             October 31, 1992, version 2.1
  110.  * Date:             April 1, 1993, version 2.2
  111.  *
  112.  * This modification of Douglas Thomson's code is released into the
  113.  * public domain, Frank Davis.   You may distribute it freely.
  114.  */
  115.  
  116. #include "tdestr.h"
  117. #include "common.h"
  118. #include "tdefunc.h"
  119. #include "define.h"
  120.  
  121.  
  122. /*
  123.  * Name:    get_replacement_flags
  124.  * Purpose: To input find and replace flags.
  125.  * Date:    June 5, 1991
  126.  * Passed:  line:  prompt line
  127.  * Returns: OK if flags were entered, ERROR if user wanted to abort
  128.  */
  129. int  get_replacement_flags( int line )
  130. {
  131. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  132. register int c;
  133. int  func;
  134. int  rc;
  135.  
  136.    save_screen_line( 0, line, line_buff );
  137.    eol_clear( 0, line, g_display.text_color );
  138.    /*
  139.     * options: prompt or no prompt (p/n)?
  140.     */
  141.    s_output( find1, line, 0, g_display.message_color );
  142.    xygoto( strlen( find1 ) + 2, line );
  143.    do {
  144.       c = getkey( );
  145.       func = getfunc( c );
  146.    } while (c != 'P'  &&  c != 'p'  &&  c != 'N'  &&  c != 'n'  &&
  147.             c != RTURN  &&  c != ESC  &&  func != AbortCommand);
  148.    restore_screen_line( 0, line, line_buff );
  149.    switch (c) {
  150.       case 'P' :
  151.       case 'p' :
  152.       case RTURN :
  153.          g_status.replace_flag = PROMPT;
  154.          rc = OK;
  155.          break;
  156.       case 'N' :
  157.       case 'n' :
  158.          g_status.replace_flag = NOPROMPT;
  159.          rc = OK;
  160.          break;
  161.       default :
  162.          rc = ERROR;
  163.    }
  164.    bm.search_defined = rc;
  165.    return( rc );
  166. }
  167.  
  168.  
  169. /*
  170.  * Name:    ask_replace
  171.  * Purpose: Ask user if he wants to (r)place, (s)kip, or (e)xit.
  172.  * Date:    June 5, 1991
  173.  * Returns: TRUE if user wants to replace, ERROR otherwise.
  174.  * Passed:  window:   pointer to current window
  175.  *          finished: TRUE if user pressed ESC or (e)xit.
  176.  */
  177. int  ask_replace( WINDOW *window, int *finished )
  178. {
  179. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  180. register int c;
  181. int  func;
  182. int  prompt_line;
  183. int  rc;
  184.  
  185.    prompt_line = window->cline - 1;
  186.    c = 39 - (strlen( find2 ) >> 1);
  187.    save_screen_line( 0, prompt_line, line_buff );
  188.    /*
  189.     * replace skip exit (r/s/e)?
  190.     */
  191.    s_output( find2, prompt_line, c, g_display.message_color );
  192.    do {
  193.       c = getkey( );
  194.       func = getfunc( c );
  195.    } while (c != 'R' && c != 'r' && c != 'S' && c != 's' && c != 'E' && c != 'e'
  196.           && c != ESC  &&  func != AbortCommand);
  197.    restore_screen_line( 0, prompt_line, line_buff );
  198.    switch (c) {
  199.       case 'R' :
  200.       case 'r' :
  201.          rc = OK;
  202.          break;
  203.       case 'E' :
  204.       case 'e' :
  205.          *finished = TRUE;
  206.       case 'S' :
  207.       case 's' :
  208.          rc = ERROR;
  209.          break;
  210.       default :
  211.          *finished = TRUE;
  212.          rc = ERROR;
  213.          break;
  214.    }
  215.    return( rc );
  216. }
  217.  
  218.  
  219. /*
  220.  * Name:    ask_wrap_replace
  221.  * Purpose: After a wrap, ask user if he wants to (q)uit or (c)ontine.
  222.  * Date:    June 5, 1991
  223.  * Returns: TRUE if user wants to continue, ERROR otherwise.
  224.  * Passed:  window:   pointer to current window
  225.  *          finished: TRUE if user pressed ESC or (q)uit.
  226.  */
  227. int  ask_wrap_replace( WINDOW *window, int *finished )
  228. {
  229. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  230. register int c;
  231. int  func;
  232. int  prompt_line;
  233. int  rc;
  234.  
  235.    prompt_line = window->bottom_line;
  236.    save_screen_line( 0, prompt_line, line_buff );
  237.    /*
  238.     * search has wrapped. continue or quit (c/q)?
  239.     */
  240.    set_prompt( find3, prompt_line );
  241.    do {
  242.       c = getkey( );
  243.       func = getfunc( c );
  244.    } while (c != 'Q'  &&  c != 'q'  &&  c != 'C'  &&  c != 'c' &&
  245.           c != ESC  &&  func != AbortCommand);
  246.    restore_screen_line( 0, prompt_line, line_buff );
  247.    switch (c) {
  248.       case 'C' :
  249.       case 'c' :
  250.          rc = OK;
  251.          break;
  252.       case 'Q' :
  253.       case 'q' :
  254.       default :
  255.          *finished = TRUE;
  256.          rc = ERROR;
  257.          break;
  258.    }
  259.    return( rc );
  260. }
  261.  
  262.  
  263. /*
  264.  * Name:    do_replace
  265.  * Purpose: To replace text once match has been found.
  266.  * Date:    June 5, 1991
  267.  * Passed:  window:     pointer to current window
  268.  *          direction:  direction of search
  269.  */
  270. void do_replace( WINDOW *window, int direction )
  271. {
  272. int  old_len;           /* length of original text */
  273. int  new_len;           /* length of replacement text */
  274. int  rcol;
  275. register int net_change;
  276. char *source;           /* source of block move */
  277. char *dest;             /* destination of block move */
  278.  
  279.    old_len = strlen( g_status.pattern );
  280.    new_len = strlen( g_status.subst );
  281.    net_change = new_len - old_len;
  282.    rcol = window->rcol;
  283.  
  284.    /*
  285.     * move the text to either make room for the extra replacement text
  286.     *  or to close up the gap left
  287.     */
  288.  
  289.    g_status.copied = FALSE;
  290.    copy_line( window->ll );
  291.    detab_linebuff( );
  292.  
  293.    if (net_change != 0) {
  294.       assert( rcol + old_len >= 0);
  295.       assert( net_change <= rcol + old_len );
  296.  
  297.       source = g_status.line_buff + rcol + old_len;
  298.       dest  = source + net_change;
  299.  
  300.       assert( g_status.line_buff_len - rcol - net_change >= 0 );
  301.       assert( g_status.line_buff_len - rcol - net_change < MAX_LINE_LENGTH );
  302.  
  303.       memmove( dest, source, g_status.line_buff_len - rcol - net_change );
  304.       g_status.line_buff_len += net_change;
  305.    }
  306.  
  307.    /*
  308.     * insert the replacement text
  309.     */
  310.  
  311.    assert( rcol >= 0 );
  312.    assert( rcol < MAX_LINE_LENGTH );
  313.    assert( g_status.line_buff_len >= 0 );
  314.    assert( g_status.line_buff_len >= rcol );
  315.  
  316.    for (dest=g_status.line_buff+rcol, source=g_status.subst; *source;)
  317.       *dest++ = *source++;
  318.  
  319.    entab_linebuff( );
  320.    window->file_info->modified = TRUE;
  321.    un_copy_line( window->ll, window, TRUE );
  322.    window->ll->dirty = TRUE;
  323.  
  324.    if (direction == FORWARD && net_change > 0)
  325.       window->rcol += net_change;
  326.  
  327.    assert( window->rcol >= 0 );
  328.    show_avail_mem( );
  329. }
  330.  
  331.  
  332. /*
  333.  * Name:    find_string
  334.  * Purpose: To set up and perform a find operation.
  335.  * Date:    June 5, 1991
  336.  * Passed:  window:  pointer to current window
  337.  * Notes:   Keep the search string and boyer-moore stuff until changed.
  338.  */
  339. int  find_string( WINDOW *window )
  340. {
  341. int  direction;
  342. int  new_string;
  343. char pattern[MAX_COLS];  /* text to be found */
  344. long found_line;
  345. line_list_ptr ll;
  346. register WINDOW *win;  /* put window pointer in a register */
  347. int  rc;
  348. int  old_rcol;
  349. int  rcol;
  350.  
  351.    switch (g_status.command) {
  352.       case FindForward :
  353.          direction = FORWARD;
  354.          new_string = TRUE;
  355.          break;
  356.       case FindBackward :
  357.          direction = BACKWARD;
  358.          new_string = TRUE;
  359.          break;
  360.       case RepeatFindForward1 :
  361.       case RepeatFindForward2 :
  362.          direction = FORWARD;
  363.          new_string = FALSE;
  364.          break;
  365.       case RepeatFindBackward1 :
  366.       case RepeatFindBackward2 :
  367.          direction = BACKWARD;
  368.          new_string = FALSE;
  369.          break;
  370.       default :
  371.          direction = 0;
  372.          new_string = 0;
  373.          assert( FALSE );
  374.          break;
  375.    }
  376.    win = window;
  377.    entab_linebuff( );
  378.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  379.       return( ERROR );
  380.  
  381.    /*
  382.     * get search text, using previous as default
  383.     */
  384.    if (new_string == TRUE) {
  385.       *pattern = '\0';
  386.       if (bm.search_defined == OK) {
  387.  
  388.          assert( strlen( (char *)bm.pattern ) < MAX_COLS );
  389.  
  390.          strcpy( pattern, (char *)bm.pattern );
  391.       }
  392.  
  393.       /*
  394.        * string to find:
  395.        */
  396.       if (get_name( find4, win->bottom_line, pattern,
  397.                     g_display.message_color ) != OK  ||  *pattern == '\0')
  398.          return( ERROR );
  399.       bm.search_defined = OK;
  400.  
  401.       assert( strlen( pattern ) < MAX_COLS );
  402.  
  403.       strcpy( (char *)bm.pattern, pattern );
  404.       build_boyer_array( );
  405.    }
  406.  
  407.    rc = OK;
  408.    if (bm.search_defined == OK) {
  409.       old_rcol = win->rcol;
  410.       if (mode.inflate_tabs)
  411.          win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  412.       update_line( win );
  413.       show_search_message( SEARCHING, g_display.diag_color );
  414.       if (direction == FORWARD) {
  415.          if ((ll = forward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
  416.             if (g_status.wrapped && g_status.macro_executing)
  417.                rc = ask_wrap_replace( win, &new_string );
  418.             if (rc == OK)
  419.                find_adjust( win, ll, found_line, rcol );
  420.          }
  421.       } else {
  422.          if ((ll = backward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
  423.             if (g_status.wrapped && g_status.macro_executing)
  424.                rc = ask_wrap_replace( win, &new_string );
  425.             if (rc == OK)
  426.                find_adjust( win, ll, found_line, rcol );
  427.          }
  428.       }
  429.       if (g_status.wrapped)
  430.          show_search_message( WRAPPED, g_display.diag_color );
  431.       else
  432.          show_search_message( CLR_SEARCH, g_display.mode_color );
  433.       if (ll == NULL) {
  434.          /*
  435.           * string not found
  436.           */
  437.          if (mode.inflate_tabs)
  438.             win->rcol = old_rcol;
  439.          combine_strings( pattern, find5a, (char *)bm.pattern, find5b );
  440.          error( WARNING, win->bottom_line, pattern );
  441.          rc = ERROR;
  442.       }
  443.       show_curl_line( win );
  444.       make_ruler( win );
  445.       show_ruler( win );
  446.    } else {
  447.       /*
  448.        * find pattern not defined
  449.        */
  450.       error( WARNING, win->bottom_line, find6 );
  451.       rc = ERROR;
  452.    }
  453.    return( rc );
  454. }
  455.  
  456.  
  457. /*
  458.  * Name:    build_boyer_array
  459.  * Purpose: To set up the boyer array for forward and backward searches.
  460.  * Date:    June 5, 1991
  461.  * Notes:   Set up one array for forward searches and another for backward
  462.  *          searches.  If user decides to ignore case then fill in array
  463.  *          with reverse case characters so both upper and lower case
  464.  *          characters are defined.
  465.  */
  466. void build_boyer_array( void )
  467. {
  468.  
  469.    /*
  470.     * set up for forward search
  471.     */
  472.    if (g_status.command == DefineSearchAndSeize  ||
  473.                            g_status.command == RepeatSearchAndSeize) {
  474.  
  475.       assert( strlen( (char *)sas_bm.pattern ) + 1 < MAX_COLS );
  476.  
  477.       memcpy( bm.pattern, sas_bm.pattern, strlen( (char *)sas_bm.pattern ) +1 );
  478.       bm.search_defined = OK;
  479.    }
  480.  
  481.    if (bm.search_defined == OK) {
  482.       build_forward_skip( &bm );
  483.       bm.forward_md2 = calculate_forward_md2( (char *)bm.pattern,
  484.                                                 bm.pattern_length );
  485.  
  486.       /*
  487.        * set up for backward search
  488.        */
  489.       build_backward_skip( &bm );
  490.       bm.backward_md2 = calculate_backward_md2( (char *)bm.pattern,
  491.                                                   bm.pattern_length );
  492.    }
  493.  
  494.  
  495.    /*
  496.     * build an array for search and seize.
  497.     */
  498.    if (sas_bm.search_defined == OK) {
  499.       build_forward_skip( &sas_bm );
  500.       sas_bm.forward_md2 = calculate_forward_md2( (char *)sas_bm.pattern,
  501.                                                     sas_bm.pattern_length );
  502.  
  503.       /*
  504.        * set up for backward search
  505.        */
  506.       build_backward_skip( &sas_bm );
  507.       sas_bm.backward_md2 = calculate_backward_md2( (char *)sas_bm.pattern,
  508.                                                       sas_bm.pattern_length );
  509.    }
  510. }
  511.  
  512.  
  513. /*
  514.  * Name:    build_forward_skip
  515.  * Purpose: build Boyer-Moore forward skip array
  516.  * Date:    October 31, 1992
  517.  * Passed:  bmp:  pointer to Boyer-Moore structure
  518.  * Notes:   build standard Boyer-Moore forward skip array.
  519.  *          Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a
  520.  *           bug in TDE 1.3 when building the ignore skip index array.
  521.  */
  522. void build_forward_skip( boyer_moore_type *bmp )
  523. {
  524. register unsigned char *p;
  525. register int i;
  526.  
  527.    assert( strlen( (char *)bmp->pattern ) < MAX_COLS );
  528.  
  529.    i = bmp->pattern_length = (int)strlen( (char *)bmp->pattern );
  530.  
  531.    /*
  532.     * set skip index of all characters to length of string
  533.     */
  534.    memset( bmp->skip_forward, i, 256 );
  535.    i--;
  536.  
  537.    /*
  538.     * for each character in string, set the skip index
  539.     */
  540.    for (p=bmp->pattern; i>=0; i--, p++) {
  541.  
  542.       assert( (char)i < bmp->skip_forward[*p] );
  543.  
  544.       bmp->skip_forward[*p] = (char)i;
  545.       if (mode.search_case == IGNORE) {
  546.          if (*p >= 'A' && *p <= 'Z') {
  547.  
  548.             assert( (char)i < bmp->skip_forward[*p+32] );
  549.  
  550.             bmp->skip_forward[*p+32] = (char)i;
  551.          } else if (*p >= 'a' && *p <= 'z') {
  552.  
  553.             assert( (char)i < bmp->skip_forward[*p-32] );
  554.  
  555.             bmp->skip_forward[*p-32] = (char)i;
  556.          }
  557.       }
  558.    }
  559. }
  560.  
  561.  
  562. /*
  563.  * Name:    build_backward_skip
  564.  * Purpose: build Boyer-Moore backward skip array
  565.  * Date:    October 31, 1992
  566.  * Passed:  bmp:  pointer to Boyer-Moore structure
  567.  * Notes:   build standard Boyer-Moore backward skip array.
  568.  *          Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a
  569.  *           bug in TDE 1.3 when building the ignore skip index array.
  570.  */
  571. void build_backward_skip( boyer_moore_type *bmp )
  572. {
  573. register unsigned char *p;
  574. register int i;
  575.  
  576.    i = -bmp->pattern_length;
  577.    memset( bmp->skip_backward, i, 256 );
  578.    i++;
  579.    for (p=bmp->pattern + bmp->pattern_length - 1; i<=0; i++, p--) {
  580.  
  581.       assert( (char)i > bmp->skip_backward[*p] );
  582.  
  583.       bmp->skip_backward[*p] = (char)i;
  584.       if (mode.search_case == IGNORE) {
  585.          if (*p >= 'A' && *p <= 'Z') {
  586.  
  587.             assert( (char)i > bmp->skip_backward[*p+32] );
  588.  
  589.             bmp->skip_backward[*p+32] = (char)i;
  590.          } else if (*p >= 'a' && *p <= 'z') {
  591.  
  592.             assert( (char)i > bmp->skip_backward[*p-32] );
  593.  
  594.             bmp->skip_backward[*p-32] = (char)i;
  595.          }
  596.       }
  597.    }
  598. }
  599.  
  600.  
  601. /*
  602.  * Name:    calculate_forward_md2
  603.  * Purpose: Calculate mini delta2 for forward searches
  604.  * Date:    October 31, 1992
  605.  * Passed:  p:  pointer to pattern
  606.  *          len: length of pattern
  607.  * Notes:   Hume and Sunday (see above) demonstrate in their paper that
  608.  *            using a simple shift function on mismatches with BM
  609.  *            gives one of the fastest run times for general text searching.
  610.  *          mini delta2 is, from the end of the string, the first leftmost
  611.  *            occurrence of the rightmost character.  mini delta2 is 1 in
  612.  *            the worst case.  in previous versions of TDE, the shift function
  613.  *            was hard-coded as 1 -- the worst case.  typically, mini delta2
  614.  *            will be the length of the search pattern.
  615.  */
  616. int  calculate_forward_md2( char *p, int len )
  617. {
  618. int  last_c;
  619. register int i;
  620. register int md2;
  621.  
  622.    md2 = 1;
  623.    i = len - 1;
  624.    last_c = p[i];
  625.    if (mode.search_case == IGNORE) {
  626.       last_c = tolower( last_c );
  627.       for (i--; i >= 0  &&  last_c != tolower( p[i] ); i--)
  628.          ++md2;
  629.    } else
  630.       for (i--; i >= 0  &&  last_c != p[i]; i--)
  631.          ++md2;
  632.  
  633.    assert( md2 >= 1  &&  md2 <= len );
  634.  
  635.    return( md2 );
  636. }
  637.  
  638.  
  639. /*
  640.  * Name:    calculate_backward_md2
  641.  * Purpose: Calculate mini delta2 for backward searches
  642.  * Date:    October 31, 1992
  643.  * Passed:  p:  pointer to pattern
  644.  *          len: length of pattern
  645.  * Notes:   the backward mini delta2 is, from the start of the string, the
  646.  *            first rightmost occurrence of the leftmost character.  in the
  647.  *            worst case, mini delta2 is -1.  typically, mini delta2 is the
  648.  *            negative length of the search pattern.
  649.  */
  650. int  calculate_backward_md2( char *p, int len )
  651. {
  652. int  first_c;
  653. register int i;
  654. register int md2;
  655.  
  656.    md2 = -1;
  657.    i = 1;
  658.    first_c = *p;
  659.    if (mode.search_case == IGNORE) {
  660.       first_c = tolower( first_c );
  661.       for (; i < len  &&  first_c != tolower( p[i] ); i++)
  662.          --md2;
  663.    } else
  664.       for (; i < len  &&  first_c != p[i]; i++)
  665.          --md2;
  666.  
  667.    assert( md2 <= -1  &&  md2 >= -len );
  668.  
  669.    return( md2 );
  670. }
  671.  
  672.  
  673. /*
  674.  * Name:    forward_boyer_moore_search
  675.  * Purpose: search forward for pattern using boyer array
  676.  * Passed:  window:  pointer to current window
  677.  *          rline:   pointer to real line counter
  678.  *          rcol:    pointer to real column variable
  679.  * Returns: position in file if found or NULL if not found
  680.  * Date:    June 5, 1991
  681.  * Notes:   Start searching from cursor position to end of file.  If we hit
  682.  *          end of file without a match, start searching from the beginning
  683.  *          of file to cursor position.  (do wrapped searches)
  684.  */
  685. line_list_ptr forward_boyer_moore_search( WINDOW *window, long *rline,
  686.      int *rcol )
  687. {
  688. register int len;
  689. int  i;
  690. int  end;
  691. register WINDOW *win;  /* put window pointer in a register */
  692. line_list_ptr ll;
  693.  
  694.    /*
  695.     * if cursor is beyond end of line then start at end of line
  696.     */
  697.    win  = window;
  698.    i = win->rcol + 1;
  699.    len = win->ll->len;
  700.    if (i > len)
  701.       i = len;
  702.    if (i < 0)
  703.       i = 0;
  704.  
  705.    *rcol = i;
  706.    *rline = win->rline;
  707.    ll = search_forward( win->ll, rline, (size_t *)rcol );
  708.  
  709.    if (ll == NULL) {
  710.  
  711.       end = 0;
  712.       if (win->ll->next != NULL) {
  713.          end = win->ll->next->len;
  714.          win->ll->next->len = EOF;
  715.       }
  716.  
  717.       /*
  718.        * haven't found pattern yet - now search from beginning of file
  719.        */
  720.       g_status.wrapped = TRUE;
  721.  
  722.       *rcol = 0;
  723.       *rline = 1L;
  724.       ll = search_forward( win->file_info->line_list, rline, (size_t *)rcol );
  725.  
  726.       if (ll == win->ll  &&  *rcol >= win->rcol)
  727.          ll = NULL;
  728.  
  729.       if (win->ll->next != NULL)
  730.          win->ll->next->len = end;
  731.    }
  732.  
  733.    if (ll != NULL)
  734.       bin_offset_adjust( win, *rline );
  735.    return( ll );
  736. }
  737.  
  738.  
  739. /*
  740.  * Name:    search_forward
  741.  * Purpose: search forward for pattern using boyer array
  742.  * Passed:  ll:     pointer to current node in linked list
  743.  *          rline:  pointer to real line counter
  744.  *          offset: offset into ll->line to begin search
  745.  * Returns: position in file if found or NULL if not found
  746.  * Date:    January 8, 1992
  747.  * Notes:   mini delta2 is the first leftmost occurrence of the rightmost
  748.  *            character.
  749.  */
  750. line_list_ptr search_forward( line_list_ptr ll, long *rline, size_t *offset )
  751. {
  752. register int i;
  753. text_ptr p;
  754. text_ptr q;
  755. int  mini_delta2;
  756. int  pat_len;
  757. int  len_s;
  758. text_ptr s;
  759. char *skip;
  760. boyer_moore_type *bmp;
  761.  
  762.    if (ll->len == EOF)
  763.       return( NULL );
  764.    else {
  765.       if (g_status.command == DefineSearchAndSeize ||
  766.           g_status.command == RepeatSearchAndSeize)
  767.          bmp = &sas_bm;
  768.       else
  769.          bmp = &bm;
  770.  
  771.       pat_len  = bmp->pattern_length;
  772.       mini_delta2 = bmp->forward_md2;
  773.       skip = bmp->skip_forward;
  774.       p    = bmp->pattern;
  775.  
  776.       i = pat_len - 1;
  777.  
  778.       s = ll->line;
  779.       s += *offset;
  780.       len_s = ll->len - *offset;
  781.       for (;;) {
  782.          /*
  783.           * Boyer-Moore fast skip loop.  check character count as we move
  784.           *   down the line.
  785.           */
  786.          for (s+=i, len_s-=i; len_s > 0 && (i = skip[(unsigned char)*s]);
  787.                               s+=i, len_s-=i);
  788.          if (len_s > 0) {
  789.             /*
  790.              * i == 0, possible match.  Boyer-Moore slow match loop.
  791.              */
  792.             q = s + 1 - pat_len;
  793.             if (mode.search_case == MATCH) {
  794.                for (i=0; i < pat_len; i++)
  795.                   if (q[i] != p[i])
  796.                      goto shift_func;
  797.             } else {
  798.                for (i=0; i < pat_len; i++)
  799.                   if (tolower( q[i] ) != tolower( p[i] ))
  800.                      goto shift_func;
  801.             }
  802.             *offset = (size_t)(q - ll->line);
  803.  
  804.             assert( *offset <= (unsigned)(ll->len - pat_len) );
  805.  
  806.             return( ll );
  807.          }
  808. shift_func:
  809.          if (len_s <= 0) {
  810.             ++*rline;
  811.             ll = ll->next;
  812.             s = ll->line;
  813.             if (ll->len == EOF)
  814.                return( NULL );
  815.             len_s = ll->len;
  816.             i = pat_len - 1;
  817.          } else
  818.             i = mini_delta2;
  819.       }
  820.    }
  821. }
  822.  
  823.  
  824. /*
  825.  * Name:    backward_boyer_moore_search
  826.  * Purpose: search backward for pattern using boyer array
  827.  * Passed:  window:  pointer to current window
  828.  *          rline:   pointer current real line counter
  829.  *          rcol:    pointer to real column
  830.  * Returns: position in file if found or NULL if not found
  831.  * Date:    June 5, 1991
  832.  * Notes:   Start searching from cursor position to beginning of file. If we
  833.  *          hit beginning end of file without a match, start searching from the
  834.  *          end of file to cursor position.  (do wrapped searches)
  835.  */
  836. line_list_ptr backward_boyer_moore_search( WINDOW *window, long *rline, int *rcol )
  837. {
  838. int  i;
  839. int  len;
  840. int  end;
  841. register WINDOW *win;  /* put window pointer in a register */
  842. line_list_ptr ll;
  843.  
  844.    win  = window;
  845.    *rline = win->rline;
  846.  
  847.    /*
  848.     * see if cursor is on EOF line.  if so, move search start to previous node.
  849.     */
  850.    if (win->ll->len != EOF) {
  851.       ll = win->ll;
  852.       i  = win->rcol - 1;
  853.       i += bm.pattern_length - 1;
  854.       len = ll->len;
  855.       if (i >= len)
  856.          i = len - 1;
  857.    } else {
  858.       ll = win->ll->prev;
  859.       --*rline;
  860.       i = 0;
  861.       if (ll != NULL)
  862.          i = ll->len - 1;
  863.    }
  864.    *rcol = i;
  865.    ll = search_backward( ll, rline, (size_t *)rcol );
  866.  
  867.    if (ll == NULL  &&  win->rline <= win->file_info->length) {
  868.  
  869.       end = 0;
  870.       if (win->ll->prev != NULL) {
  871.          end = win->ll->prev->len;
  872.          win->ll->prev->len = EOF;
  873.       }
  874.  
  875.       /*
  876.        * haven't found pattern yet - now search from end of file
  877.        */
  878.       g_status.wrapped = TRUE;
  879.       ll = win->file_info->line_list_end;
  880.       if (ll->prev != NULL)
  881.          *rcol = ll->prev->len;
  882.       else
  883.         *rcol = 0;
  884.       *rline = win->file_info->length;
  885.       ll = search_backward( ll->prev, rline, (size_t *)rcol );
  886.  
  887.       if (ll == win->ll  &&  *rcol <= win->rcol)
  888.          ll = NULL;
  889.  
  890.       if (win->ll->prev != NULL)
  891.          win->ll->prev->len = end;
  892.    }
  893.    if (ll != NULL)
  894.       bin_offset_adjust( win, *rline );
  895.    return( ll );
  896. }
  897.  
  898.  
  899. /*
  900.  * Name:    search_backward
  901.  * Purpose: search backward for pattern using boyer array
  902.  * Passed:  ll:  pointer to node in linked list to start search
  903.  *          rline:  pointer to real line counter
  904.  *          offset:  offset into ll->line to start search
  905.  * Returns: position in file if found else return NULL
  906.  * Date:    January 8, 1992
  907.  * Notes:   Start searching from cursor position to beginning of file.
  908.  *          mini delta2 is the first rightmost occurrence of the leftmost character.
  909.  */
  910. line_list_ptr search_backward( line_list_ptr ll, long *rline, size_t *offset )
  911. {
  912. register int i;
  913. text_ptr p;
  914. int  mini_delta2;
  915. int  pat_len;
  916. int  len_s;
  917. text_ptr s;
  918.  
  919.    if (ll == NULL)
  920.       return( NULL );
  921.    if (ll->len == EOF)
  922.       return( NULL );
  923.    else {
  924.       mini_delta2 = bm.backward_md2;
  925.       pat_len  = bm.pattern_length;
  926.       p = bm.pattern;
  927.  
  928.       i = -bm.pattern_length + 1;
  929.  
  930.       s = ll->line;
  931.       s += *offset;
  932.       len_s = *offset + 1;
  933.       for (;;) {
  934.  
  935.          /*
  936.           * Boyer-Moore fast skip loop.  check character count as we move
  937.           *   up the line.
  938.           */
  939.          for (s+=i, len_s+=i; len_s > 0 &&
  940.                  (i = bm.skip_backward[(unsigned char)*s]); s+=i, len_s+=i);
  941.          if (len_s > 0) {
  942.             /*
  943.              * i == 0, possible match.  Boyer-Moore slow match loop.
  944.              */
  945.             if (mode.search_case == MATCH) {
  946.                for (i=0; i < pat_len; i++)
  947.                   if (s[i] != p[i])
  948.                     goto shift_func;
  949.             } else {
  950.                for (i=0; i < pat_len; i++)
  951.                   if (tolower( s[i] ) != tolower( p[i] ))
  952.                      goto shift_func;
  953.             }
  954.             *offset =(size_t)(s - ll->line);
  955.  
  956.             assert( *offset <= (unsigned)(ll->len - pat_len) );
  957.  
  958.             return( ll );
  959.          }
  960. shift_func:
  961.          if (len_s <= 0) {
  962.             --*rline;
  963.             ll = ll->prev;
  964.             if (ll == NULL)
  965.                return( NULL );
  966.             if (ll->len == EOF)
  967.                return( NULL );
  968.             len_s = ll->len;
  969.             s = ll->line + len_s - 1;
  970.             i = 1 - pat_len;
  971.          } else
  972.             i = mini_delta2;
  973.       }
  974.    }
  975. }
  976.  
  977.  
  978. /*
  979.  * Name:    show_search_message
  980.  * Purpose: display search status
  981.  * Date:    January 8, 1992
  982.  * Passed:  i:     index into message array
  983.  *          color: color to display message
  984.  */
  985. void show_search_message( int i, int color )
  986. {
  987.    /*
  988.     *  0 = blank
  989.     *  1 = wrapped...
  990.     *  2 = searching
  991.     *  3 = replacing
  992.     */
  993.    assert( i >= 0  &&  i <= 3);
  994.    s_output( find7[i], g_display.mode_line, 67, color );
  995. }
  996.  
  997.  
  998. /*
  999.  * Name:    bin_offset_adjust
  1000.  * Purpose: place cursor on screen given a position in file - default cline
  1001.  * Date:    June 5, 1991
  1002.  * Passed:  window:  pointer to current window
  1003.  *          rline:   real line position some where in the file
  1004.  * Notes:   in binary mode, we keep an accurate count of the offset of the
  1005.  *          cursor from the beginning of the file.
  1006.  */
  1007. void bin_offset_adjust( WINDOW *window, long rline )
  1008. {
  1009. line_list_ptr node;
  1010. long found_distance;
  1011.  
  1012.    assert( rline >= 1L  &&  rline <= window->file_info->length );
  1013.  
  1014.    found_distance = window->rline - rline;
  1015.    node = window->ll;
  1016.    if (found_distance < 0) {
  1017.       while (found_distance++ < 0) {
  1018.          window->bin_offset += node->len;
  1019.          node = node->next;
  1020.       }
  1021.    } else if (found_distance > 0) {
  1022.       while (found_distance-- > 0) {
  1023.          node = node->prev;
  1024.          window->bin_offset -= node->len;
  1025.       }
  1026.    }
  1027.    assert( window->bin_offset >= 0 );
  1028.  }
  1029.  
  1030.  
  1031. /*
  1032.  * Name:    find_adjust
  1033.  * Purpose: place cursor on screen given a position in file - default cline
  1034.  * Date:    June 5, 1991
  1035.  * Passed:  window:  pointer to current window
  1036.  *          ll:   position anywhere in file
  1037.  *          rline:  real line number of ll in the file
  1038.  *          rcol:   real column of ll in the file
  1039.  * Notes:   ll could be anywhere in file.  Find the start of line that
  1040.  *          ll is on.  Determine if start of line is behind or ahead of
  1041.  *          current line.  Once that is done, it is easy to determine if ll
  1042.  *          is on screen.  Lastly, current cursor position becomes start of
  1043.  *          ll line - reposition and display.
  1044.  */
  1045. void find_adjust( WINDOW *window, line_list_ptr ll, long rline, int rcol )
  1046. {
  1047. int  cmd;
  1048. long test_line;
  1049. file_infos *file;
  1050. register WINDOW *win;  /* put window pointer in a register */
  1051.  
  1052.    win = window;
  1053.    file = win->file_info;
  1054.  
  1055.    /*
  1056.     * find real column found is on.
  1057.     */
  1058.    if (mode.inflate_tabs)
  1059.       rcol = detab_adjust_rcol( ll->line, rcol );
  1060.  
  1061.    /*
  1062.     * if p, start of found line, is greater than current line, see if
  1063.     * p is between current line and bottom line on screen.
  1064.     */
  1065.    if (win->rline < rline) {
  1066.       /*
  1067.        * test_line is the number of lines between rline and found line.
  1068.        */
  1069.       test_line = rline - win->rline;
  1070.       if ((long)win->cline + test_line <= (long)win->bottom_line)
  1071.          win->cline += (int)test_line;
  1072.       else
  1073.          file->dirty = LOCAL;
  1074.  
  1075.    /*
  1076.     * if p, start of found line, is less than current line, see if
  1077.     * p is between current line and top line on screen.
  1078.     */
  1079.    } else if (win->rline > rline) {
  1080.       test_line = win->rline - rline;
  1081.       if ((long)win->cline - test_line > (long)(win->top_line+win->ruler-1))
  1082.          win->cline -= (int)test_line;
  1083.       else
  1084.          file->dirty = LOCAL;
  1085.       if (rline < (long)(win->cline - (win->top_line+win->ruler-1)))
  1086.          win->cline = (int)rline + win->top_line+win->ruler - 1;
  1087.    }
  1088.  
  1089.    /*
  1090.     * cursor line becomes found line.  check if column is on screen.
  1091.     */
  1092.    win->rline = rline;
  1093.    win->ll    = ll;
  1094.    if (file->dirty == LOCAL && (win->cline == win->bottom_line ||
  1095.                                 win->cline == win->top_line + win->ruler)) {
  1096.       cmd = g_status.command;
  1097.       if (cmd == RepeatFindForward1    ||  cmd == RepeatFindBackward1 ||
  1098.           cmd == DefineDiff            ||  cmd == RepeatDiff          ||
  1099.           cmd == DefineSearchAndSeize  ||  cmd == RepeatSearchAndSeize) {
  1100.          center_window( win );
  1101.       } else if (cmd == ReplaceString) {
  1102.          if (win->visible)
  1103.             center_window( win );
  1104.       }
  1105.    }
  1106.    check_virtual_col( win, rcol, rcol );
  1107. }
  1108.  
  1109.  
  1110. /*
  1111.  * Name:    replace_string
  1112.  * Purpose: To set up and perform a replace operation.
  1113.  * Date:    June 5, 1991
  1114.  * Passed:  window:  pointer to current window
  1115.  */
  1116. int  replace_string( WINDOW *window )
  1117. {
  1118. int  direction;
  1119. char pattern[MAX_COLS];  /* the old and replacement text */
  1120. int  net_change;
  1121. int  sub_len;
  1122. int  file_changed;
  1123. int  finished;
  1124. int  rc;
  1125. int  rcol;
  1126. int  rcol_limit;
  1127. int  wrapped;
  1128. line_list_ptr ll;
  1129. long found_line;
  1130. long line_limit;
  1131. WINDOW wp;
  1132. register WINDOW *win;  /* put window pointer in a register */
  1133. int  visible;
  1134.  
  1135.    win = window;
  1136.    direction = get_replace_direction( win );
  1137.    if (direction == ERROR)
  1138.       return( ERROR );
  1139.  
  1140.    entab_linebuff( );
  1141.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  1142.       return( ERROR );
  1143.  
  1144.    /*
  1145.     * get the search pattern, using the previous as the default
  1146.     */
  1147.    *pattern = '\0';
  1148.    if (g_status.replace_defined == OK) {
  1149.  
  1150.       assert( strlen( g_status.pattern ) < MAX_COLS );
  1151.  
  1152.       strcpy( pattern, g_status.pattern );
  1153.    }
  1154.  
  1155.    /*
  1156.     * string to find
  1157.     */
  1158.    if (get_name( find9, win->bottom_line, pattern,
  1159.                  g_display.message_color ) != OK  ||  *pattern == '\0')
  1160.       return( ERROR );
  1161.  
  1162.    assert( strlen( pattern ) < MAX_COLS );
  1163.  
  1164.    strcpy( g_status.pattern, pattern );
  1165.  
  1166.    /*
  1167.     * get the replacement text, using the previous as the default
  1168.     */
  1169.    *pattern = '\0';
  1170.    if (g_status.replace_defined == OK) {
  1171.  
  1172.       assert( strlen( g_status.subst ) < MAX_COLS );
  1173.  
  1174.       strcpy( pattern, g_status.subst );
  1175.    }
  1176.    if (get_name( find10, win->bottom_line, pattern,
  1177.                   g_display.message_color ) != OK  ||  *pattern == '\0')
  1178.       return( ERROR );
  1179.  
  1180.    assert( strlen( pattern ) < MAX_COLS );
  1181.  
  1182.    strcpy( g_status.subst, pattern );
  1183.    sub_len = strlen( pattern );
  1184.    strcpy( (char *)bm.pattern, g_status.pattern );
  1185.    net_change = sub_len - strlen( g_status.pattern );
  1186.  
  1187.    /*
  1188.     * get the replace flags, Prompt or NoPrompt
  1189.     */
  1190.    if (get_replacement_flags( win->bottom_line ) != OK)
  1191.       return( ERROR );
  1192.  
  1193.    build_boyer_array( );
  1194.    dup_window_info( &wp, win );
  1195.    update_line( win );
  1196.    g_status.replace_defined = OK;
  1197.  
  1198.    if (mode.inflate_tabs)
  1199.       win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol );
  1200.  
  1201.    rc = OK;
  1202.    visible = win->visible;
  1203.    if (g_status.replace_flag == NOPROMPT) {
  1204.       wp.visible = FALSE;
  1205.       xygoto( win->ccol, win->cline );
  1206.       show_search_message( REPLACING, g_display.diag_color );
  1207.    }
  1208.    wrapped = FALSE;
  1209.    finished = FALSE;
  1210.    file_changed = FALSE;
  1211.    line_limit = 0;
  1212.    rcol_limit = 0;
  1213.    if (direction == FORWARD) {
  1214.       if ((ll = forward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1215.                 !g_status.control_break) {
  1216.          line_limit = found_line;
  1217.          rcol_limit = rcol;
  1218.          replace_and_display( &wp, ll, found_line, rcol, &finished,
  1219.                                &file_changed, direction );
  1220.       } else {
  1221.          /*
  1222.           * string not found
  1223.           */
  1224.          error( WARNING, win->bottom_line, find8 );
  1225.          finished = TRUE;
  1226.          rc = ERROR;
  1227.       }
  1228.       while (finished == FALSE) {
  1229.          if (wp.visible == TRUE)
  1230.             update_line( &wp );
  1231.          if ((ll = forward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1232.              !g_status.control_break) {
  1233.             if (g_status.wrapped)
  1234.                wrapped = TRUE;
  1235.             if (wrapped) {
  1236.                if (found_line > line_limit)
  1237.                   finished = TRUE;
  1238.                else if (found_line == line_limit  &&  rcol == rcol_limit)
  1239.                   finished = TRUE;
  1240.             }
  1241.             if (finished == FALSE) {
  1242.                rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1243.                                          &file_changed, direction );
  1244.                if (rc == OK && ll == win->ll && rcol < rcol_limit)
  1245.                   rcol_limit += net_change;
  1246.             }
  1247.          } else {
  1248.             if (g_status.control_break)
  1249.                rc = getkey( );
  1250.             /*
  1251.              * string not found     or   control break
  1252.              */
  1253.             if (g_status.control_break)
  1254.                error( WARNING, win->bottom_line, cb );
  1255.             else if (wp.visible)
  1256.                error( WARNING, win->bottom_line, find8 );
  1257.             finished = TRUE;
  1258.             rc = ERROR;
  1259.          }
  1260.       }
  1261.    } else {
  1262.       if ((ll = backward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1263.           !g_status.control_break) {
  1264.          line_limit = found_line;
  1265.          rcol_limit = rcol;
  1266.          replace_and_display( &wp, ll, found_line, rcol, &finished, &file_changed,
  1267.                               direction );
  1268.       } else {
  1269.          /*
  1270.           * string not found
  1271.           */
  1272.          error( WARNING, win->bottom_line, find8 );
  1273.          finished = TRUE;
  1274.          rc = ERROR;
  1275.       }
  1276.       while (finished == FALSE) {
  1277.          if (wp.visible == TRUE)
  1278.             update_line( &wp );
  1279.          if ((ll = backward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1280.              !g_status.control_break) {
  1281.             if (g_status.wrapped)
  1282.                wrapped = TRUE;
  1283.             if (wrapped) {
  1284.                if (found_line < line_limit)
  1285.                   finished = TRUE;
  1286.                else if (found_line == line_limit  &&  rcol == rcol_limit)
  1287.                   finished = TRUE;
  1288.             }
  1289.             if (finished == FALSE) {
  1290.                rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1291.                                          &file_changed, direction );
  1292.                if (rc == OK && found_line == line_limit && rcol < rcol_limit)
  1293.                   rcol_limit += net_change;
  1294.             }
  1295.          } else {
  1296.             if (g_status.control_break)
  1297.                rc = getkey( );
  1298.             /*
  1299.              * string not found    or   control break
  1300.              */
  1301.             if (g_status.control_break)
  1302.                error( WARNING, win->bottom_line, cb );
  1303.             else if (wp.visible)
  1304.                error( WARNING, win->bottom_line, find8 );
  1305.             finished = TRUE;
  1306.             rc = ERROR;
  1307.          }
  1308.       }
  1309.    }
  1310.  
  1311.    if (mode.inflate_tabs)
  1312.       win->rcol = detab_adjust_rcol( win->ll->line, win->rcol );
  1313.  
  1314.    if (g_status.replace_flag == PROMPT)
  1315.       dup_window_info( win, &wp );
  1316.    else {
  1317.       show_search_message( CLR_SEARCH, g_display.mode_color );
  1318.       g_status.wrapped = FALSE;
  1319.    }
  1320.    win->visible = visible;
  1321.    check_virtual_col( win, win->rcol, win->ccol );
  1322.    if (win->file_info->dirty != LOCAL && win->file_info->dirty != GLOBAL)
  1323.       show_curl_line( win );
  1324.    if (file_changed)
  1325.       win->file_info->modified = TRUE;
  1326.    make_ruler( win );
  1327.    show_ruler( win );
  1328.    show_ruler_pointer( win );
  1329.    return( rc );
  1330. }
  1331.  
  1332.  
  1333. /*
  1334.  * Name:    replace_and_display
  1335.  * Purpose: To make room for replacement string
  1336.  * Date:    June 5, 1991
  1337.  * Passed:  window:            pointer to current window
  1338.  *          ll:                pointer to position of pattern in file
  1339.  *          rline:             pointer to real line counter
  1340.  *          rcol:              pointer to real column
  1341.  *          finished:          stop replacing on this occurrence?
  1342.  *          modified:          skip this replacement?
  1343.  *          direction:         direction of search
  1344.  * Notes:   Show user where pattern_location is on screen if needed.
  1345.  *          Replace and display if needed.   Always ask the user if he
  1346.  *          wants to do wrapped replacing.
  1347.  */
  1348. int  replace_and_display( WINDOW *window, line_list_ptr ll, long rline,
  1349.                      int rcol, int *finished, int *modified, int direction )
  1350. {
  1351. register int rc;
  1352. file_infos *file;
  1353. register WINDOW *win;  /* put window pointer in a register */
  1354.  
  1355.    win = window;
  1356.    file = win->file_info;
  1357.    rc = OK;
  1358.    if (g_status.wrapped) {
  1359.       rc = ask_wrap_replace( win, finished );
  1360.       g_status.wrapped = FALSE;
  1361.       show_search_message( CLR_SEARCH, g_display.mode_color );
  1362.    }
  1363.    if (rc == OK) {
  1364.       find_adjust( win, ll, rline, rcol );
  1365.       if (win->visible == TRUE) {
  1366.          make_ruler( win );
  1367.          show_ruler( win );
  1368.          show_ruler_pointer( win );
  1369.          xygoto( win->ccol, win->cline );
  1370.          if (file->dirty) {
  1371.             display_current_window( win );
  1372.             file->dirty = FALSE;
  1373.          } else
  1374.             show_curl_line( win );
  1375.       }
  1376.  
  1377.       if (g_status.replace_flag == PROMPT && rc == OK) {
  1378.          show_line_col( win );
  1379.          rc = ask_replace( win, finished );
  1380.       }
  1381.       if (rc == OK) {
  1382.          do_replace( win, direction );
  1383.          *modified = TRUE;
  1384.          file->dirty = GLOBAL;
  1385.          if (win->visible == TRUE) {
  1386.             show_changed_line( win );
  1387.             file->dirty = FALSE;
  1388.          }
  1389.       }
  1390.       if (mode.inflate_tabs)
  1391.          win->rcol = rcol;
  1392.    }
  1393.    return( rc );
  1394. }
  1395.  
  1396.  
  1397. /*
  1398.  * Name:    scan_forward
  1399.  * Purpose: To find the corresponding occurrence of target, ignoring
  1400.  *           embedded pairs of opp and target, searching forwards.
  1401.  * Date:    June 5, 1991
  1402.  * Passed:  rline:  pointer to real line position
  1403.  *          rcol:   pointer to real column position
  1404.  *          ll:     pointer to current node in linked list
  1405.  *          opp:    the opposite to target
  1406.  *          target: the string to be found
  1407.  *          rc:     OK if found, ERROR otherwise
  1408.  * Returns: the location of the corresponding target in the text buffer
  1409.  * Notes:   Every 8,000 characters, check pointer forward.
  1410.  */
  1411. line_list_ptr scan_forward( long *rline, int *rcol, line_list_ptr ll,
  1412.                             char opp, char target, int *rc )
  1413. {
  1414. text_ptr s;
  1415. int  count = 0;          /* number of unmatched opposites found */
  1416. int  len;
  1417. register char c;
  1418.  
  1419.    *rc = OK;
  1420.    if (ll != NULL  &&  ll->len != EOF) {
  1421.       len = ll->len - *rcol - 1;
  1422.       s = ll->line + *rcol + 1;
  1423.       while (ll->len != EOF) {
  1424.          while (len > 0) {
  1425.  
  1426.             assert( s != NULL);
  1427.  
  1428.             c = *s++;
  1429.             --len;
  1430.             if (opp == c)
  1431.                count++;
  1432.             else if (target == c) {
  1433.                if (count == 0)
  1434.                  goto match;
  1435.                --count;
  1436.             }
  1437.          }
  1438.          ++*rline;
  1439.          ll  = ll->next;
  1440.          s   = ll->line;
  1441.          len = ll->len;
  1442.       }
  1443. match:
  1444.       if (ll->len != EOF) {
  1445.  
  1446.          assert( s != NULL );
  1447.  
  1448.          *rcol = (int)(s - ll->line - 1);
  1449.       } else
  1450.          *rc = ERROR;
  1451.    } else
  1452.       *rc = ERROR;
  1453.  
  1454.    if (*rc == OK) {
  1455.       assert( *rcol >= 0 );
  1456.       assert( *rcol < ll->len );
  1457.    }
  1458.  
  1459.    return( ll );
  1460. }
  1461.  
  1462.  
  1463. /*
  1464.  * Name:    scan_backward
  1465.  * Purpose: To find the corresponding occurrence of target, ignoring
  1466.  *           embedded pairs of opp and target, searching backwards.
  1467.  * Date:    June 5, 1991
  1468.  * Passed:  rline:  pointer to real line position
  1469.  *          rcol:   pointer to real column position
  1470.  *          ll:     pointer to current node in linked list
  1471.  *          opp:    the opposite to target
  1472.  *          target: the string to be found
  1473.  *          rc:     OK if found, ERROR otherwise
  1474.  * Returns: the location of the corresponding target in the text buffer
  1475.  */
  1476. line_list_ptr scan_backward( long *rline, int *rcol, line_list_ptr ll,
  1477.                              char opp, char target, int *rc )
  1478. {
  1479. text_ptr s;
  1480. int  count = 0;         /* number of unmatched opposites found */
  1481. register int len;
  1482. register char c;
  1483.  
  1484.    *rc = OK;
  1485.    if (ll != NULL  &&  ll->len != EOF) {
  1486.       s = ll->line + *rcol - 1;
  1487.       len = *rcol;
  1488.       while (ll != NULL) {
  1489.          while (len > 0) {
  1490.  
  1491.             assert( s != NULL );
  1492.  
  1493.             c = *s--;
  1494.             if (opp == c)
  1495.                count++;
  1496.             else if (target == c) {
  1497.                if (count == 0)
  1498.                  goto match;
  1499.                --count;
  1500.             }
  1501.             --len;
  1502.          }
  1503.          --*rline;
  1504.          ll = ll->prev;
  1505.          if (ll != NULL) {
  1506.             len = ll->len;
  1507.             s = ll->line + len - 1;
  1508.          }
  1509.       }
  1510. match:
  1511.       if (ll != NULL) {
  1512.  
  1513.          assert( s != NULL );
  1514.  
  1515.          *rcol = (int)(s - ll->line + 1);
  1516.       } else
  1517.          *rc = ERROR;
  1518.    } else
  1519.       *rc = ERROR;
  1520.  
  1521.    if (*rc == OK) {
  1522.       assert( *rcol >= 0 );
  1523.       assert( *rcol < ll->len );
  1524.    }
  1525.  
  1526.    return( ll );
  1527. }
  1528.  
  1529.  
  1530. /*
  1531.  * Name:    match_pair
  1532.  * Purpose: To find the corresponding pair to the character under the
  1533.  *           cursor.
  1534.  * Date:    June 5, 1991
  1535.  * Passed:  window:  pointer to current window
  1536.  * Notes:   Searching is very simple-minded, and does not cope with things
  1537.  *          like brackets embedded within quoted strings.
  1538.  */
  1539. int  match_pair( WINDOW *window )
  1540. {
  1541. long rline;
  1542. char c;
  1543. register WINDOW *win;  /* put window pointer in a register */
  1544. int  rc;
  1545. int  rcol;
  1546. line_list_ptr ll;
  1547.  
  1548.    win = window;
  1549.    entab_linebuff( );
  1550.    rline = win->rline;
  1551.    ll = win->ll;
  1552.    if (un_copy_line( ll, win, TRUE ) == ERROR)
  1553.       return( ERROR );
  1554.    /*
  1555.     * make sure the character under the cursor is one that has a
  1556.     *  matched pair
  1557.     */
  1558.    if (ll->len == EOF || win->rcol >= ll->len)
  1559.       return( ERROR );
  1560.    rcol = win->rcol;
  1561.    c = *(ll->line + rcol);
  1562.    rc = OK;
  1563.  
  1564.    /*
  1565.     * find the matching pair
  1566.     */
  1567.    switch (c) {
  1568.       case '[':
  1569.          ll = scan_forward( &rline, &rcol, ll, '[', ']', &rc );
  1570.          break;
  1571.       case '(':
  1572.          ll = scan_forward( &rline, &rcol, ll, '(', ')', &rc );
  1573.          break;
  1574.       case '{':
  1575.          ll = scan_forward( &rline, &rcol, ll, '{', '}', &rc );
  1576.          break;
  1577.       case ']':
  1578.          ll = scan_backward( &rline, &rcol, ll, ']', '[', &rc );
  1579.          break;
  1580.       case ')':
  1581.          ll = scan_backward( &rline, &rcol, ll, ')', '(', &rc );
  1582.          break;
  1583.       case '}':
  1584.          ll = scan_backward( &rline, &rcol, ll, '}', '{', &rc );
  1585.          break;
  1586.       default :
  1587.          rc = ERROR;
  1588.    }
  1589.  
  1590.    /*
  1591.     * now show the user what we have found
  1592.     */
  1593.    if (rc == OK) {
  1594.       update_line( win );
  1595.       bin_offset_adjust( win, rline );
  1596.       find_adjust( win, ll, rline, rcol );
  1597.       if (!win->file_info->dirty)
  1598.          show_curl_line( win );
  1599.       make_ruler( win );
  1600.       show_ruler( win );
  1601.    }
  1602.    return( rc );
  1603. }
  1604.